package com.stefan.sort;

/*以第一个元素作为有序列，后面的和它比较，大的移动数组，然后插入，指针后一
* i=1 (data[i] 就是无序的第一个比较元素)， j=i-1 （data[j]就是有序的最后一个元素）
* 时间复杂度O(n^2)
* 最好的情况是O(n)
* */
public class InsertionSort {
    public static void main(String[] args) {
        int[] data = {7,9,3,2,4,6,0,5,1,8};
        System.out.print("排序前：");
        for (int m = 0; m < data.length; m++) {
            System.out.print(data[m]);
        }
        System.out.println("");
        int len = data.length;
        for (int i = 1; i < len; i++) { //从1开始，是第一个元素data[0]不用排序，归入排好序的部分。0-i是排好序的，i后面是要比较的值
            int current = data[i]; //未排序的开始，也就是要进行比较的那个元素
            int j = i-1;
            for (;j>=0; j--) {
                if (data[j] > current) {
                    data[j+1] = data[j];
//                    data[j+1] = pre;
                } else {
                    break; // 当前要比较的元素比排好序的元素中的一个大，那就停止比较
                }
            }
            data[j+1] = current;
            System.out.print("第"+i+"轮后：");
            for (int m = 0; m < len; m++) {
                System.out.print(data[m]);
            }
            System.out.println("");
        }

    }
}
